package com.example.algorithm.model;

/**
 *
 * NO.68 最小栈
 * @auth Administrator
 * @create @2024/8/5@22:37
 * @decription
 * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 *
 * 实现 MinStack 类:
 *
 * MinStack() 初始化堆栈对象。
 * void push(int val) 将元素val推入堆栈。
 * void pop() 删除堆栈顶部的元素。
 * int top() 获取堆栈顶部的元素。
 * int getMin() 获取堆栈中的最小元素
 **/

import lombok.Data;

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 *
 * 解法一：辅助栈
 * 解法二：单个栈
 * 解法三：链表
 * 解法四：数组
 *
 *
 */


@Data
public class MinStack {
   private  Node head;


    public MinStack() {

    }

    public void push(int val) {
        if(head==null){
            head = new Node(val,val);
        }else{
            head=new Node(val,Math.min(val,head.min),head);
        }

    }

    public void pop() {
        head=head.next;
    }

    public int top() {
     return  head.val;
    }

    public int getMin() {
        return  head.min;
    }


    class Node{
         int val;
         int min;
         Node next;

         Node(int val,int min, Node next){
             this.val =val;
             this.min=min;
             this.next = next;
         }

         Node(int val, int min) {
            this(val, min, null);
        }


    }
}
